Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 2
з дисципліни
«Математичні методи дослідження операцій»
Симплекс-метод розв’язку задач
лінійного програмування
Виконав:
студент гр. КН-4
Львів – 2008
Мета роботи: набуття навиків розв’язування задач лінійного програмування (ЗЛП) симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях у середовищі Еxcel
Порядок роботи:
Заповнити початкову симплекс-таблицю ЗЛП згідно заданого варіанту завдання.
Використовуючи засоби роботи з адресацією в Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування.
Знайти оптимальний розв’язок і максимальне та мінімальне значення цільової функції.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком:
назва роботи;
мета роботи;
порядок виконання роботи;
короткі теоретичні відомості;
алгоритм побудови розв’язку задачі;
малюнки відповідних таблиць;
одержані результати, їх аналіз і висновки.
Короткі теоретичні відомості про симплекс-метод розв’язування ЗЛП.
Симплекс-метод, який відомий ще як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, причому так, що значення цільової функції зростають. Оптимальний розв’язок знаходиться при цьому за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також відповісти на запитання: чи може бути взагалі розв’язаною конкретна задача лінійного програмування.
Методикою побудови розв’язку, яка найкраще піддається формалізації й алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць.
Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, причому всі вільні члени мають бути додатні:
Ap = [A1, ..., An, e1, ..., em, A0]. (1)
До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення.
Алгоритм розв’язування задачі лінійного програмування, наприклад, задачі максимізації методом симплекс-таблиць складатиметься з наступних кроків:
Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді
2. За напрямний стовпець Aj вибирають той, для якого
EMBED Equation.2 . (2)
3. Напрямний рядок вибирається за умовою:
EMBED Equation.2 . (3)
4. Виконується крок симплекс-перетворення з напрямним елементом aij, використовуючи співвідношення:
а) для елементів напрямного рядка
EMBED Equation.2 , l = 0, 1, ..., n; (4)
б) для елементів напрямного стовпця
EMBED Equation.2 ; r = 1, 2, ..., m, причому r i; EMBED Equation.2 ; (5)
в) для решти елементів матриці
EMBED Equation.2 , l j, r i. (6)
г) для елементів індексного рядка
EMBED Equation.2 , EMBED Equation.2 , l = 1, 2, ..., n. (7)
Правильність обчислень перевіряється за формулами
EMBED Equation.2 , EMBED Equation.2 . (8)
Нарешті, в стовпці Bx треба замінити xi на xj, а в стовпці C замінити ci на cj.
5. Якщо, всі елементи симплекс-рядка EMBED Equation.2 , l = 1, 2, ..., n, то новий базисний розв’язок EMBED Equation.2 , EMBED Equation.2 є оптимальним. У випадку, коли ця умова не виконується, переходиться на крок 2 і виконується наступна ітерація.
6. Другий, третій і четвертий кроки повторюються до тих пір, доки одна з ітерацій не завершиться одним із двох результатів:
а) всі EMBED Equation.2 , l = 1, 2, ..., n. Умова оптимальності базису останньої таблиці;
б) знайдеться такий a0j = j < 0, ...
